package main

import "fmt"

/*
*
Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

利用快慢指针

循环查找
当fast.Forward==nil 或者fast=slow时跳出循环
为什么不能一个指针不动 另一个指针单步走来检查呢?
![20180810153384179440826.png](http://cdn.bsummer.cn/20180810153384179440826.png)

| 应用场景        | 快指针步数     | 慢指针步数   | 结果                         |
| ----------- | --------- | ------- | -------------------------- |
| 判断是否有环      | 2         | 1       | 若相遇则有环                     |
| 找环入口（142）   | 2 → 1     | 1       | 相遇后 fast=1 再次相遇即入口         |
| 找中点（奇偶）     | 2         | 1       | slow 落在中点（左/右中点看 fast 初始值） |
| 删除倒数第 N 个节点 | fast 先走 N | slow 未动 | fast 走到尾时，slow 在倒数 N+1     |

🔍 为什么快慢指针有效？（理解后你永远不会忘）
因为链表是一维，不可反向

→ 只能单向走
→ 只能靠“速度差”来创造信息

快慢指针 = 人为引入 相对速度差
就像在环形跑道上，一个快跑一个慢跑，必定能追上。

🧠 快慢指针的能量来源：相遇点 = 信息点

这是快慢指针的灵魂。

当快慢指针相遇，就说明产生了“有意义的信息”。

如果在链表中相遇 → 有环

如果快指针提前走 N → 他们的距离可控（倒数第 N 个节点）

如果快指针每两步一步 → slow 自然停在中点（找中点）

相遇不是副作用，是目的。
*/
type ListNode struct {
	Val  int
	Next *ListNode
}

func main() {

	a := ListNode{Val: 1, Next: nil}
	b := ListNode{Val: 2, Next: nil}
	c := ListNode{Val: 3, Next: nil}
	a.Next = &b
	b.Next = &c
	c.Next = &a

	fmt.Println(hasCycle(&a))
}

func hasCycle(head *ListNode) bool {
	if head == nil {
		return false
	}

	fast := head
	slow := head
	for fast != nil && fast.Next != nil { //注意次序 fast的判断要在fast.Next之前
		slow = slow.Next
		fast = fast.Next.Next

		if fast == slow {
			return true
		}
	}
	return false
}

func hadCycle(head *ListNode) bool {
	if head == nil {
		return false
	}

	p, q := head, head
	// 安全访问q.Next.Next
	for q != nil && q.Next != nil {
		p = p.Next
		q = q.Next.Next
		if p == q {
			return true
		}
	}
	return false
}
